////https://www.luogu.com.cn/problem/P1757
//
//#include<iostream>
//#include<vector>
//using namespace std;
//
//const int N = 1010;
//int dp[N];
//vector<vector<int>> a(N), b(N);
//
//int main()
//{
//	int n, m; cin >> m >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		int x, y, z;
//		cin >> x >> y >> z;
//		a[z].push_back(x); b[z].push_back(y);	
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = m; j >= 0; j--)
//		{
//			for (int k = 0; k < a[i].size(); k++)
//			{
//				if (j - a[i][k] < 0) continue;
//				dp[j] = max(dp[j], dp[j - a[i][k]] + b[i][k]);
//			}
//		}
//	}
//	cout << dp[m] << endl;
//	return 0;
//}